#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/08/14
# @Author   :Changshu
# @File     :practice_53.py
# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

'''贪心算法
def maxSubArray(nums:list)->int:
	preSum=0
	maxSum=nums[0]
	for i in range(0,len(nums)):
		preSum=max(preSum+nums[i],nums[i])
		maxSum=max(preSum,maxSum)
	return maxSum
'''

'''分治算法'''
# lSum 表示 [l, r] 内以 l 为左端点的最大子段和
# rSum 表示 [l, r] 内以 r 为右端点的最大子段和
# mSum 表示 [l, r] 内的最大子段和
# iSum 表示 [l, r] 的区间和
# status={'lSum':0,'rSum':0,'mSum':0,'iSum':0}

def pushUp(l,r)->dict:
	iSum=l['iSum']+r['iSum']
	lSum=max(l['lSum'],l['iSum']+r['lSum'])		#因为是端点，所有要加全部
	rSum=max(r['rSum'],l['rSum']+r['iSum'])
	mSum=max(max(l['mSum'],r['mSum']),l['rSum']+r['lSum'])
	return {'lSum':lSum,'rSum':rSum,'mSum':mSum,'iSum':iSum}

def get(nums:list,l:int,r:int)->dict:
	if l==r:
		return {'lSum':nums[l],'rSum':nums[l],'mSum':nums[l],'iSum':nums[l]}
	m=(l+r)>>1			#向右移一位
	lStatus=get(nums,l,m)
	rStatus=get(nums,m+1,r)
	return pushUp(lStatus,rStatus)

def maxSubArray(nums:list)->int:
	return get(nums,0,len(nums)-1)['mSum']



if __name__ == '__main__':
	nums=[-2,1,-3,4,-1,2,1,-5,4]
	print(maxSubArray(nums))